|
In graph theory, a minimum cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge) that is minimal in some sense. Variations of the minimum cut include: *The cut with the minimum number of edges among all cuts in an undirected graph, determining the edge connectivity of the graph. Karger's algorithm provides an efficient randomized method for finding this cut. *A generalization of the unweighted and undirected minimum cut, the , in which the goal is to partition the graph into at least connected components by removing as few edges as possible. *Graph partition, a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut. *The cut in a flow network that separates the source and sink vertices and minimizes the total weight on the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the max-flow min-cut theorem, the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network. *A cut in a weighted undirected network that separates a particular pair of vertices from each other and has minimum possible weight. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the Gomory–Hu tree of the graph. == Stoer-Wagner Minimum Cut == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Minimum cut」の詳細全文を読む スポンサード リンク
|